package com.zp.self.module.level_4_算法练习.算法.双指针.左右指针;

import java.util.Arrays;

/**
 * @author By ZengPeng
 */
public class 力扣_16_最接近的三数之和 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_16_最接近的三数之和().threeSumClosest(new int[]{-1,2,1,-4},1));
        System.out.println(new 力扣_16_最接近的三数之和().threeSumClosest(new int[]{0,0,0},1));
    }

    /**
    题目：给你一个长度为 n 的整数数组 nums 和 一个目标值 target。
     请你从 nums 中选出三个整数，使它们的和与 target 最接近。
     返回这三个数的和。
     假定每组输入只存在恰好一个解。

     示例 1：
     输入：nums = [-1,2,1,-4], target = 1
     输出：2
     解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

     示例 2：
     输入：nums = [0,0,0], target = 1
     输出：0

    分析：【difficult】
       1.排序，双循环 ， 左右指针
            遍历记录当前绝对值最近的  sum

    边界值 & 注意点：
       1.
     **/
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int current = nums[0]+nums[1]+nums[2];
        for (int i = 0; i < nums.length; i++) {
            int left=i+1,right = nums.length-1;
            while(left<right){
                int sum =nums[i]+nums[left]+nums[right];
                if(Math.abs(sum-target)<Math.abs(current-target)) current = sum;
                if(sum>target) right--;
                else if(sum<target)left++;
                else return target;
            }
        }
        return current;
    }
}
